# 559.N叉树的最大深度
# 给定一个N叉树，找到其最大深度。
# 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
# N叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。
#
# 示例1：
# 输入：root = [1, null, 3, 2, 4, null, 5, 6]
# 输出：3
#
# 示例2：
# 输入：root = [1, null, 2, 3, 4, 5, null, null, 6, 7, null, 8, null, 9, 10, null, null, 11, null, 12, null, 13, null, null,
#            14]
# 输出：5


class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children


class Solution:
    def maxDepth(self, root: 'Node') -> int:
        def getdepth(root):
            if not root:
                return 0
            size = len(root.children)
            dep = 0
            for i in range(size):
                dep = max(dep,getdepth(root.children[i]))
            return dep + 1
        return getdepth(root)

    def maxDepth2(self, root: 'Node') -> int:
        # 层序遍历的写法
        if not root:
            return 0
        from collections import deque
        que = deque()
        que.append(root)
        count = 0
        while que:
            size = len(que)
            for i in range(size):
                node = que.popleft()
                if node.children:
                    que.extend(node.children)
            count += 1
        return count